#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };
 
class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int& pil, int ebegin, int eend)
    {
        if (ebegin > eend)
            return nullptr;
        TreeNode* root = new TreeNode(preorder[pil]);
        int cur = ebegin;
        while (cur <= eend)
        {
            if (preorder[pil] == inorder[cur])
                break;
            else
                cur++;
        }
        pil++;
        root->left = build(preorder, inorder, pil, ebegin, cur - 1);
        root->right = build(preorder, inorder, pil, cur + 1, eend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pil = 0;
        int ebegin = 0;
        int eend = inorder.size() - 1;
        return build(preorder, inorder, pil, ebegin, eend);

    }
};
int main()
{
    Solution as;
    vector<int> preorder = { 3, 9, 20, 15, 7 };
    vector<int> inorder = { 9, 3, 15, 20, 7 };
    as.buildTree(preorder,inorder);
	return 0;
}